题目大意
3sum问题的变种，寻找与目标数字最近的那一组数,返回三数之和
解题思路
一样的遍历每个数，对剩余数组进行双指针扫描。区别仅仅在于当：
sum = A[left] + A[right]
(1) sum = target时直接返回
(2) sum != target时，在相应移动left/right指针之前，先计算abs(sum-target)的值，并更新结果。
时间复杂度：O(n log n)（排序）+ O（n^2）= O（n^2）
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution:
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort() # 先排序
closest_sum = sys.maxsize
for i in range(len(nums)-2): # 遍历至倒数第三个，后面两个指针
if i == 0 or nums[i] > nums[i-1]: # 排除相同数和刚开始的时候
left = i + 1
right = len(nums) - 1
while left < right:
diff = nums[left] + nums[right] + nums[i] - target
if abs(diff) < abs(closest_sum):
closest_sum = diff
if diff == 0:
return target
elif diff < 0:
left += 1
else:
right -= 1
return closest_sum + target # 原三数之和
|
总结
该题显然是考验双指针，双指针思路清晰，更容易理解。